/*
Source : https://leetcode.com/problems/decode-ways/
Author : nflush@outlook.com
Date   : 2016-07-08
*/

/*
91. Decode Ways

    Total Accepted: 74790
    Total Submissions: 418665
    Difficulty: Medium

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Subscribe to see which companies asked this question
*/
// 8ms
class Solution {
public:
    int numDecodings(string s) {
        int a[2] = {0, 1};
        int index = 0;
        int code = 0;        
        int cur = 0;
        int pre = 1;
        if (s.size() == 0)return 0;
        for (int len = 0; len < s.size(); len++ ,index^=1, code=cur, pre = cur){
            cur = s[len] - '0';
            if (cur <= 9 && cur > 0){
                ;
            } else {
                cur = 0;
            }

            code = code * 10 + cur;
            if (code >= 1 && code <= 26 && pre){
                if (cur > 0){
                    a[index] = a[index ^1]+a[index];
                } else {
                    a[index] = a[index];
                }
            } else {
                if (cur > 0){
                    a[index] = a[index ^1];
                } else {
                    return 0;
                }
            }
//            printf("a[%d:%d], index[%d]\n",a[0], a[1], index);
        }
        return a[index^1];
    }
};

// 4ms
class Solution {
public:
    int numDecodings(string s) {
        int a[2] = {0, 1};
        int index = 0;
        int cur = 0;
        int pre = 0;
        if (s.size() == 0)return 0;
        int size = s.size();
        for (int len = 0; len < size; len++ ,index^=1, pre = cur){
            cur = s[len] - '0';
            if (cur <= 9 && cur > 0){
                if (pre && (pre * 10 + cur) <= 26){
                    a[index] = a[index ^1]+a[index];
                } else {
                    a[index] = a[index ^1];
                }
            } else {
                if (!pre || pre >2)return 0;
                cur = 0;
            }
        }
        return a[index^1];
    }
};
